The present claimed invention relates to the field of network communication. Specifically, the present claimed invention relates to an apparatus and a method for dynamically allocating time slots in multiple channels of a bandwidth over which a device may communicate in a network.
Network communications are ubiquitous in government, businesses and education. Many obstacles have arisen in the effort to better utilize network resources, to provide better quality service to users, and to provide flexible service options to users. One type of network uses multiple frequency channels over which devices may communicate. This type of network is referred to as a Broadband Access Network (BAN). Several of the obstacles for optimal utilization of a BAN will be presented along with the consequential need to solve them.
Prior Art FIG. 1a presents a block diagram of a conventional shared media network system. For exemplary purposes, four devices, e.g. Customer Premises Equipment (CPE), 104a, 104b, 104c, and 104d are coupled to a hub 102 via link 106. Link 106 can provide multiple channels of communication, typically dependent upon the transmitter/receiver capabilities of devices 104a, 104b, 104c, and 104d and the hub 102.
There are two basic methods of communicating in the present network, contention access, and reservation access. With reservation access, a device sends a request to a hub to reserve a specific length of transmission on the network. The hub processes the request, reserves a slot on the network for the requesting device, and sends instructions to the device telling it when to transmit. Subsequently, the device transmits its information according to the instructions. This process avoids collisions, but it also consumes time and resources to make and process the request. Delay sensitive applications such as Internet Telephony and video conferencing require the quality of service delivered by reservation access protocol.
On the other hand, data transmissions such as e-mail and file transfers can be more efficiently delivered by contention access protocol. With contention access, any device in a network can communicate when it has information ready to transmit and when a unused time slot appears. Unfortunately, if more than one device meets the same criteria and tries to transmit at the same time, a collision may arise. If a collision arises, the hub will send a message to the relevant devices indicating that the transmission has failed. Consequently, any device involved in a collision will have to attempt to retransmit the information. In broadband access networks similar to the one shown in Prior Art FIG. 1a, the multiple access protocol is generally a combination of reservation access and contention access for Internet access and Telephony services. A separate downlink channel is available for the hub to communicate to the devices. However, there are much fewer problems with the downlink channel than the uplink channel because a single entity, the hub, controls all transmissions on the downlink.
Prior Art FIG. 1b provides an illustration of multiple uplink channels (channels) that can be used in a hub-spoke network. It also exemplifies a conventional assignment of time slots in multiple channels over which multiple devices will communicate. The illustration presents a contention access scenario where devices communicate and hope to avoid a collision. In the example, three channels, channel AA 154, channel BB 152, and channel CC 153 are shown in parallel as they span the spectrum 164 of the network. They represent different frequency channels within the bandwidth, or spectrum 164, of the network. As shown, several packets fill up lower channel AA 154. These packets are sequentially identified as a first data packet 156a for device A 104a, a data packet 158 for device B 104b, a second data packet 156b for device A 104a, and a data packet 160 for device C 104c. This scenario illustrates that the efficiency of contention access drops when a large number of time slots in a shared channel are assigned to network devices by the reservation protocol.
Given the scenario in Prior Art FIG. 1b, a first attempt to transmit a data packet 162a for device D 104d, and a second attempt to transmit a data packet 162b for device D 104d, occur because device D 104d cannot locate an available time slot in which to transmit. Hence, device D 104d has an extended wait time for communicating, and a lower quality of service. Consequently, a need arises for a method of allowing a fairer and more consistent access to the network by devices.
One of the conventional methods of providing access to the network when one channel becomes very busy is to force the device, whose transmission is being blocked, to migrate to an empty uplink channel. In the present example, device D 104d can migrate up to channel BB 152 after repeatedly being blocked in its originally allocated channel, channel AA 154. However, this process is inefficient. Channel resources may be overburdened in one channel and underutilized in another channel. Additionally, the waiting period for the blocked device and the consequent migration process consumes valuable time and results in substandard communication performance. Consequently, a need arises for a method to more evenly utilize the multiple channel resources and thereby provide better communication performance to the user.
A user will typically transmit in just that given channel for consecutive data packets. Even if a user is forced to migrate to another channel, the user will transmit just in the new channel to which it migrated. However, sometimes two or more channels are equally busy or loaded, and assigning a device to transmit entirely on one or the other channel will cause congestion. Hence, a need arises for a method and apparatus to allow a new device to transmit on evenly loaded channels without upsetting the even loading.
As illustrated in Prior Art FIG. 1b, a device is conventionally allocated a default channel on which to transmit. This default channel conventionally remains the same for a given device. Even though different devices may be assigned to different channels in the multichannel BAN, they still maintain their default channel each time they access the network. Hence, in each channel, the bandwidth utilization can vary at any given time depending on the number of devices that are active or idle on that channel. Consequently, different channels in a multichannel network can have vastly different loading depending on whether, or when, devices log on to their allocated channel. Furthermore, the loading in each channel can be highly non-uniform if a device with a low bandwidth capability is grouped into a channel having a large bandwidth. The varied loading might mean overcrowding on one channel and unused resources on another channel.
In the present example, device A 104a, device B 104b, device C 104c, and device D 104d are all allocated to the same default channel, channel AA 154. Alternatively, these devices could have been assigned to a different default channel. The point is that, regardless of which channel they are on, once a device is assigned to a channel, the assignment does not change. As a result of this rigid convention, a need arises for a method to periodically allocate default channels in a dynamic manner to better utilize the resources on a multichannel network.
Another feature of the conventional protocol is to assign a device just a single fixed channel in which to transmit information. In conventional networking, more than one service class can be supported on a single network. However, the conventional method does not accomplish this service efficiently. The conventional method will create channel bandwidths that are specific to a service class of user.
Prior Art FIG. 1c provides an illustration of multiple uplink channels (channels) 170 for different service classes that can be used in a hub-spoke network. Similar to Prior art FIG. 1b, this new figure also exemplifies a conventional assignment of time slots in multiple channels over which devices in different service classes will communicate. While some of the same devices from Prior Art FIG. 1b are utilized here, their capabilities and requirements are different from those in Prior Art FIG. 1b. 
As an example, if a user requires a wide bandwidth, e.g. device A 104a from Prior Art FIG. 1a, then a channel will be created to satisfy the user, e.g. channel DD 174 of FIG. 1c. Channel DD has a bandwidth, dedicated to the wide bandwidth user, that is equivalent to the combination of the bandwidth from two channels of FIG. 1b. If other users in the same network require only a small bandwidth, then another channel is dedicated to their bandwidth requirement, e.g. channel EE 172. These bandwidth assignments are typically fixed and do not change. Consequently, depending upon the quantity of users actively using each service class, a channel could have wasted bandwidth because the bandwidth is reserved for a given class, but is not accessible to another class. For example, if only one user is using the large bandwidth channel DD 174, and they are not transmitting large amounts of information, then a large portion of the bandwidth is not utilized for a portion of time, e.g. time slot range 178. While a device with a narrower bandwidth might be allowed to use a channel that has a higher bandwidth, this method is still inefficient because it does not utilize the full bandwidth capability of the channel. Additionally, a wide bandwidth device cannot use a narrow bandwidth channel. Thus, for example, wide bandwidth device A, in FIG. 1c, would not be allowed to transmit on channel EE 172 even though it might need to and even though no traffic might exist on channel EE 172. Thus, the prior art was primarily limited to incrementing service based on time slots, since the channel assignments were fixed. Consequently, a need arises for a more flexible manner in which to accommodate multiple service classes on a given bandwidth while balancing channel utilization at the same time.
Another limitation of the conventional networking is the difficulty involved with changing the service class for a user. If a user has subscribed to a given service class, then a dedicated device is typically used for that specific service class. If the user wishes to change service classes, then a new device for the new service class must be obtained. This method requires time, money, and other resources to accomplish a change in service class. Furthermore, frequency channelization of the bandwidth of the network might have to be rearranged in response to a need for a new service class with a wider bandwidth. Changing the frequency channelization of a network using conventional means could be expensive and time-consuming. In view of these limitations, a need arises for a method to dynamically change the service class for a user without requiring a new device. Another need arises for a method to create a new service class without having to rearrange the frequency channelization of the network bandwidth.
Furthermore, a conventional device, e.g. 104a, 104b, 104c, and 104d is sometimes required to be a smart unit in order to accomplish some of the contention protocols and methods. That is, it is an expensive device that require a microprocessor capable of performing complicated tasks. To make the device more attractive to users, a need arises for a method to improve network performance and offer flexible service options while only requiring inexpensive dumb devices.
In summary, a need arises for a method of allowing a fairer and more consistent access to the network by devices. Additionally, a need arises for a method to more evenly utilize the multiple channel resources and thereby provide better communication performance to the user. Yet another need arises for a method and apparatus to allow a new device to transmit on evenly loaded channels without upsetting the even loading. Another need arises for a method to periodically allocate default channels in a dynamic manner to better utilize the resources on a multichannel network. Yet another need arises for a more flexible manner in which to accommodate multiple service classes on a given bandwidth while equating channel utilization at the same time. Another need arises for a method to dynamically change the service class for a user without requiring a new device. Another need arises for a method to create a new service class without having to rearrange the frequency channelization of the network bandwidth. Finally, to make the device more attractive to users, a need arises for a method to improve network performance and offer flexible service options while only requiring an inexpensive dumb device. The present invention provides a unique and novel solution that meets all the above needs.
The present invention provides a method and apparatus for dynamically allocating time slots in multiple channels of a bandwidth over which a device might communicate on the network.
In one embodiment, the present invention recites a method comprising several steps. First, a request to log onto a network is received from a new device. In the present embodiment, the network is a broadband access network (BAN). Next, a loading condition of the network is determined. The loading is determined by the quantity and identity of channels to which each existing device on a network is allocated. A quantity of channels required by new device is then determined according to the service class to which new device subscribed and to the capability of the device. An identity of a quantity of channels on which the new device is allocated to transmit information is determined.
The identity of the channels is determined according to a desired criteria for the loading condition, such as uniform loading, uniform time-slot vacancies in the multiple channels, uniform quantity of service classes in each channel, or uniform time slot assignments in the multiple channels. A time slot allocation for the new device is identified and communicated, along with the identity of the frequency of channels to the device. Then, communication from the new device is received on the allocated time slots on the allocated identity of quantity of channels. The time slot allocation is updated periodically with the update of channel loading. In this manner, the present invention allows a fairer and more consistent access to the network by devices because it can dynamically assign a channel to a device depending on the loading condition of the network. Consequently, the present invention more evenly utilizes the multiple channel resources and thereby provides better communication performance to the user. All these changes are done at the hub, and thus, the present invention only requires an inexpensive dumb device. In summary, while the prior art would allocate a device to a single channel that would change when the device encountered repeated transmission failures, the present invention evaluates and decides which of the multiple channels the device should transmit on every time it needs to communicate on the network. Consequently it provides even loading, uniform vacancies, and equitable access for all devices.
In another embodiment, the present invention recites a method for dynamically changing, or managing, the service classes on a network, comprising several steps. In one step, a request to change a service class is received from a device. For example, a user wants to change from a narrow bandwidth service class to a wide bandwidth service class because the user has an newly arisen need for transmitting more data. In that situation, a higher quantity of channels is allocated for the higher service class, thus providing a wider bandwidth. In another step, the request is verified against the transmission capability of the device and against the subscription service of the device. In another step, an updated loading condition is determined. Then, in another step, an identify of the channels over which the device can transmit in the new service class is determined based on the loading condition. Finally, the identify of the channels is determined and communicated to the device.
Thus, the present invention provides a method to dynamically change the service class for a user without requiring a new device. The present embodiment also illustrates how the present invention accommodates multiple service classes on a given network bandwidth in flexible manner, while equating channel utilization at the same time. Finally, the present invention accomplishes the methods on a hub, and thus only requires an inexpensive dumb device.